Content Addressable Memories (CAMs) are commonly used in cache systems, and other address translation systems, of high speed computing systems. They are also useful in high-speed network routers, and many other applications known in the art of computing. Ternary Content Addressable Memories (TCAMs) are ternary state CAM cells and are commonly used for parallel search of high performance computing systems.
A TCAM system is composed of TCAM blocks with arrays of TCAM cells. A TCAM system typically has a TCAM block array (M×N) that includes a plurality of rows (M) and a plurality of columns (N). Further, each row has a plurality of TCAM blocks, and each TCAM block has a plurality of TCAM cells. These arrays typically have vertically running bit lines and search lines for data read/write function and horizontal running word lines and match lines. All TCAM cells in a column share the same bit lines and search lines, whereas the word lines and match lines are shared by all cells in a row. Each TCAM cell includes a pair of memory elements and a corresponding pair of compare circuits.
The TCAM cells are characterized by circuitry capable of generating a match output for each row of TCAM blocks in the TCAM cell thereby indicating whether any location of the array contains a data pattern that matches a query input and the identity of that location. Each TCAM cell typically has the ability to store a unit of data, and the ability to compare that unit of data with a unit of query input and each TCAM block has the ability to generate a match output. In parallel data search, an input keyword is placed at the search bit lines after precharging the match lines to a power supply voltage Vdd. The data in each TCAM cell connected to a match line is compared with this data, and if there is a mismatch in any cell connected to a match line, the match line will discharge to ground through the compare circuit of that TCAM cell. A compare result indication of each TCAM block in a row is combined to produce a match signal for the row to indicate whether the row of TCAM cells contains a stored word matching a query input. The match signals from each row in the TCAM cell together constitute match output signals of the array; these signals may be encoded to generate the address of matched locations or used to select data from rows of additional memory.
Each TCAM cell in each column is typically connected to a common read/write bit line pair and search bit line pair. The common read/write bit line is used to write the data to a pair of memory cells, which can be part of a TCAM cell. Each memory cell is accessed using a word line which is decoded using an input address. The common read/write bit line is also used for reading the data from a memory cell. The differential developed across the read/write bit lines are sensed using a sense amplifier during a read cycle.
Further, each TCAM cell in each column is typically connected to a common query data line, also referred to as a common search bit line. The common search bit line enables simultaneous data searching in each CAM cell in a column from a query input. The common search data line can also be used as a write data line, when the CAM cell is based on a PMOS compare circuit.
The unit of data that is stored in a TCAM cell is ternary, having three possible states: logic one, logic zero, and don't care. To store these three states, two memory elements are needed. TCAM blocks of these TCAM cells produce a local match compare result if the query input is equal to the data stored in the CAM cells in the TCAM blocks, the query input contains a don't care state, or the data stored is a don't care data. The TCAM cells produce a mismatch result otherwise. The TCAM cells are particularly useful in address translation systems that allow variable sized allocation units.
A typical problem with TCAM cells is that they use extra transistors for search function, and therefore require large silicon area and consume more power. The resulting interconnections contribute to leakage capacitance that affects system performance. Many inventions in the field of TCAMs are aimed at solving these issues of area, power and performance. One conventional technique to reduce the silicon area and power consumption uses different NAND based compare transistors connected in series, to reduce the TCAM cell size and power consumption. However, this technique fails to perform well at lower voltages, because the voltage at the gate of the TCAM cell is equal to VDD (supply voltage)−Vt (threshold voltage). Further, this approach limits the performance.
Another conventional technique uses same bit lines for read/write as well as search to reduce the number of total bit lines per TCAM cell in an effort to reduce the silicon area. This approach requires using PMOS transistors in the compare circuit, which generally reduces the speed of operation during a compare operation. In addition, this approach requires evaluating the search bit lines during write operation, which results in the dissipation of a large amount of power. Yet another conventional technique to minimize area uses DRAM based memory circuitry. But this approach is not suitable for speed sensitive applications such as cache memories since the dynamic refreshing required by DRAMs slows down the system operation.
Another significant problem of TCAMs is capacitance effects due to large number of match lines and bit lines, and the associated interconnect capacitances. Parallel searching requires high power and for large arrays, bit line capacitances are significant. Some approaches to circumvent this problem have been to reduce the number of bit lines and number of interconnections and the length of interconnections. Shorter lines reduce the line capacitances and thereby reduce the power dissipation.